{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# On-Site Question 1 - SOLUTION\n",
    "\n",
    "## Problem\n",
    "\n",
    "** Given a list of integers and a target number, write a function that returns a boolean indicating if its possible to sum two integers from the list to reach the target number **\n",
    "\n",
    "## Requirements\n",
    "\n",
    "** Try pen/paper before coding out your solution **\n",
    "\n",
    "** You can not use an integer element twice. Optimize for time over space **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Solution\n",
    "\n",
    "For this problem we will take advantage of a **set** data structure. We will make a single pass through the list of integers, treating each element as the first integer of our possible sum.\n",
    "\n",
    "At each iteration we will check to see if there is a second integer which will allow us hit the target number, adn we will use a set to check if we've already seen it in our list.\n",
    "\n",
    "We will then update our seen set by adding the current number in the iteration to it.\n",
    "\n",
    "Let's see this coded out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solution(lst,target):\n",
    "    \n",
    "    # Create set to keep track of duplicates\n",
    "    seen = set()\n",
    "    \n",
    "    # We want to find if there is a num2 that sums with num to reach the target\n",
    "    \n",
    "    for num in lst:\n",
    "        \n",
    "        num2 = target - num\n",
    "        \n",
    "        if num2 in seen:\n",
    "            return True\n",
    "        \n",
    "        seen.add(num)\n",
    "        \n",
    "    # If we never find a pair match which creates the sum\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution([1,3,5,1,7],4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution([1,3,5,1,7],14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
